/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        //注意：链表总结点数大于等于k
        //倒数第k个即为正序第n-k+1个，需遍历链表两次

        //链表为空
        if(!head)  return head;

        ListNode* pHead = head;
        //统计链表长度
        int length = 1;
        while(pHead->next){
            pHead = pHead->next;
            ++length;
        }

        if(length < k)  return NULL;

        //从头开始寻找
        int resultptr = length - k + 1;
        int n = 1;
        while(n < resultptr){
            head = head->next;
            ++n;
        }

        return head;
        
        
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        //注意：链表总结点数大于等于k
        //倒数第k个即为正序第n-k+1个
        /*
        双指针遍历：只需遍历一次
        指针front先行，到达第k - 1时停止，此时第二个指针end也开始行动；
        两个指针的距离始终保持（k - 1），这样当front到达末尾时，end刚好指向倒数第k个结点
        */

        //检查输入的合法性
        if(!head || k <= 0)  return NULL;

        ListNode* front = head;
        ListNode* end = head;
        int n = 1;  //到n = k时停止
        while((n < k) && (front->next)){
            front = front->next;
            ++n;
        }
        if(n < k)  return NULL;  //k超出链表长度

        while(front->next){
            front = front->next;
            end = end->next;
        }

        return end;  
    }
};